# coding=utf-8

"""
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [0,1,1,2,1,2]

Follow up:

    It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
    Space complexity should be O(n).
    Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
"""

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        def hammingWeight(n):
        	cnt = 0
        	while n != 0:
        		n &= n - 1
        		cnt += 1
        	return cnt

        res = []
        for i in range(num+1):
        	res.append(hammingWeight(i))
        return res


class Solution1(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]

        状态方程为 P(x) = P(x&(x-1)) + 1

        """

        res = [0] * (num + 1)
        for i in xrange(1, num + 1):
            res[i] = res[i & (i - 1)] + 1

        return res
